In modern coding systems, values of a source signal are mapped to a smaller set of values which are called quantization values. Such coding may be performed by a lossy coder as shown in FIG. 1.
The lossy coding system comprises a quantizer 101 that implements a mapping from a value of the input signal into a so-called quantization index, a lossless coder 103 that performs conversion of the quantization index into a binary codeword (“Code”) that will be stored and/or transmitted to represent the signal value and at least one reconstructor 105 that comprises lossless decoder and inverse quantizer (a mapping form a reconstructed index to the signal reconstruction) providing signal reconstruction. The quantizer 101 and the reconstructor 105 conduct a trade-off between the rate, usually in bits/sample, that the lossless coder can achieve and a distortion defined on the source and its reconstruction. The lossless coder 103 aims to produce the shortest code given the quantization indices.
The minimum expected rate is known to be the per-sample entropy of the sequence being encoded as described in T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. John Wiley & Sons, 2006, which can be achieved by entropy coding paradigms. Widely used entropy coding methods include the Lempel-Ziv code as described in J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Transactions on Information Theory, vol. 23, no. 3, pp. 337-343, 1977., the Huffman code as described in D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the IRE, vol. 40, no. 9, pp. 1098-1101, 1952., and the arithmetic coding [P. G. Howard and J. S. Vitter, “Arithmetic coding for data compression,” Proceedings of the IEEE, vol. 82, no. 6, pp. 857-865, 1994.]. The Lempel-Ziv code as described in J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Transactions on Information Theory, vol. 23, no. 3, pp. 337-343, 1977, achieves the optimal rate when the sequence is ergodic and the length of the sequence approaches infinity. It does not require any statistical model or any explicit modeling of the input, which makes it universal.
However, due to the strong condition for optimality and the ignorance of model, it usually brings worse performance than other methods in practice as described in G. R. Kuduvalli and R. M. Rangayyan, “Performance analysis of reversible image compression techniques for high-resolution digital teleradiology,” IEEE Transactions on Medical Imaging, vol. 11, no. 3, pp. 430-445, 1992., and in S. Dorward, D. Huang, S. A. Savari, G. Schuller, and B. Yu, “Low delay perceptually lossless coding of audio signals,” in Proc. DCC 2001. Data Compression Conf, 2001, pp. 312-320.
The Huffman code uses a probabilistic model and can perform well for short and/or non-ergodic sequences. However, it encodes the entire sequence at once to approach the optimality, thus incurring large delay and computational complexity. It is known that the optimal code length can be achieved more efficiently by coding the samples sequentially, in light of the chain rule of the entropy:
                                          a            )                    ⁢                                          ⁢                      H            ⁡                          (                                                Q                  1                                ,                …                ⁢                                                                  ,                                  Q                  N                                            )                                      =                              ∑                          i              =              1                        N                    ⁢                                          ⁢                                    H              ⁡                              (                                                                            Q                      i                                        ❘                                          Q                      1                                                        ,                  …                  ⁢                                                                          ,                                      Q                                          i                      -                      1                                                                      )                                      .                                              (        1        )            
This can be implemented by entropy coders that facilitate fractional code length such as the arithmetic coding. The key to sequential entropy coding is to obtain the conditional probability distribution of a sample given all samples ahead of it. The conditional probability, since it depends on all the past samples, may require a prohibitive computational effort. To address this problem, while maintaining the sequential coding manner, commonly two strategies are employed predictive coding and Markovian assumption.
Predictive coding aims to transform the source by prediction such that quantizing the transformed source leads to independent indices. Exact independence of the quantization indices is only achievable in special situations, e.g., when the prediction is open-loop and the source is a Gaussian process, or when both the source and the quantization noise are Gaussian processes in the case of closed-loop prediction as described in R. Zamir, Y. Kochman, and U. Erez, “Achieving the Gaussian rate-distortion function by prediction,” IEEE Transactions on Information Theory, vol. 54, no. 7, pp. 3354-3364, 2008.
It shall be noted that although the open-loop prediction has a lighter requirement for achieving the independence of quantization indices, it is less commonly used because it leads to a poorer rate-distortion trade-off than closed-loop prediction in practical coders, and proves to be unable to meet the rate-distortion function in theory as described in K. T. Kim and T. Berger, “Sending a lossy version of the innovations process is suboptimal in QG rate-distortion,” in Proc. Int. Symp. Information Theory ISIT 2005, 2005, pp. 209-213.
The other technique for computationally inexpensive entropy coding is to assume Markovianity of the quantization indices, meaning that the conditional probability of a sample depends only on a subset of its preceding samples. However, the Markovianity of the quantization indices is a strong assumption. Particularly, even if the source is Markovian, the quantization may damage this property.
Due to a non-linear nature of quantization it is, however, often difficult estimate the probability of a quantization index, in particular, to capture and exploit the statistical dependency between the quantization indices.
In practice, the statistical dependencies between the quantization indices are often neglected or a zero-order entropy coding is performed, which may lead to a degraded coding performance. Alternatively, one may consider usage of high-order entropy coding, which is able to capture the statistical dependencies between the quantization indices. However, it may be associated with a large computational complexity.